package com.mlamp;


import sun.reflect.generics.tree.Tree;

import java.util.*;

/**
 * 给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
 * 3
 * / \
 * 9  20
 * /  \
 * 15   7
 */
public class 锯齿形层次遍历算法103 {

    public static void main(String[] args) {

        Integer[] integers = {
                3,
                9, 20,
                null, null, 15, 7,
                null, null, null, null, 1, 2, 5, 6
        };

        锯齿形层次遍历算法103 instance = new 锯齿形层次遍历算法103();
        //instance.resolve(Arrays.asList(integers));
    }


    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) return result;

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        boolean isRever = false;
        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> curLevel = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                TreeNode cur = queue.poll();
                if (cur.left != null) {
                    queue.offer(cur.left);
                }
                if (cur.right != null) {
                    queue.offer(cur.right);
                }
                if (isRever) {
                    curLevel.add(0, cur.value);
                } else {
                    curLevel.add(cur.value);
                }
            }
            isRever = !isRever;
            result.add(curLevel);
        }
        return result;
    }


    //bad design
    public void resolve(List<Integer> arrays) {
        Queue<TreeNode> queue = new ArrayDeque<>();
        List<List<Integer>> results = new ArrayList<>();
        if (queue.isEmpty()) queue.add(TreeNode.of(arrays.get(0), true, 0, 0));
        while (!queue.isEmpty()) {
            TreeNode poll = queue.poll();
            List<Integer> integers = new ArrayList<>();
            if (results.isEmpty() || results.size() <= poll.level) {
                results.add(poll.level, integers);
            } else {
                integers = results.get(poll.level);
            }
            integers.add(poll.value);
            System.out.println(poll);
            if (poll != null) {
                if (poll.index * 2 + 1 > arrays.size()) continue;
                if (poll.odd) {
                    queue.add(TreeNode.of(arrays.get(poll.index * 2 + 1), false, poll.index * 2 + 1, poll.level + 1));
                    queue.add(TreeNode.of(arrays.get((poll.index + 1) * 2), false, 2 * (poll.index + 1), poll.level + 1));
                } else {
                    queue.add(TreeNode.of(arrays.get((poll.index + 1) * 2), true, 2 * (poll.index + 1), poll.level + 1));
                    queue.add(TreeNode.of(arrays.get(poll.index * 2 + 1), true, poll.index * 2 + 1, poll.level + 1));
                }
            }
        }
        for (List<Integer> items : results) {
            System.out.println(Arrays.toString(items.toArray()));
        }
    }

    //[3,9,20,null,null,15,7]
    public void buildTree(int[] array) {


    }

    private static final class TreeNode {
        public Integer value;
        public TreeNode left;
        public TreeNode right;
        public Boolean odd;
        public Integer index;
        public Integer level;


        private static final TreeNode of(Integer value) {
            return new TreeNode(value);
        }

        private static final TreeNode of(Integer value, Boolean odd) {
            return new TreeNode(value, odd);
        }

        private static final TreeNode of(Integer value, Boolean odd, Integer index) {
            return new TreeNode(value, odd, index);
        }

        private static final TreeNode of(Integer value, Boolean odd, Integer index, Integer level) {
            return new TreeNode(value, odd, index, level);
        }

        public TreeNode(Integer value) {
            this.value = value;
            this.odd = true;
            this.left = null;
            this.right = null;
        }

        public TreeNode(Integer valuem, Boolean odd) {
            this(valuem);
            this.odd = odd;
        }

        public TreeNode(Integer value, Boolean odd, Integer index) {
            this(value, odd);
            this.index = index;
        }

        public TreeNode(Integer value, Boolean odd, Integer index, Integer level) {
            this(value, odd, index);
            this.level = level;
        }

        @Override
        public String toString() {
            return "TreeNode{" +
                    "value=" + value +
                    ", left=" + left +
                    ", right=" + right +
                    ", odd=" + odd +
                    ", index=" + index +
                    ", level=" + level +
                    '}';
        }
    }
}
